149. Max Points on a Line(Linkedin Hard)(Java)

作者:JY

题目：Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

分析：题目给出二维点，我们需要求最大的共线点的个数，看到题目我们需要思考如何判断最多的共线点，点(x1, y1)，(x2, y2)，(x3, y3)三点共线条件是：(y2-y1)/(x2-x1) = (y3-y1)/(x3-x1)，对于每个点p出发，对与该点到所有点的斜率我们需要计算出来，判断相同数值的总和其中最多的个数加1（出发点p）即为最多的共线点。但是还有两点特殊情况需要考虑，当x1 = x2，y1!=y2时，为垂直连线，计算斜率时分母为0会出错。
当x1 = x2，y1 = y2时，两点重合，则(x2, y2)和所有(x1, y1)的连线共线。

题解1:Brute Force
n个点总共构成n*(n-1)/2条直线，然后对每条直线看看是有多少点在直线上，记录最大值，最后返回结果。而判断一个点i在j,k构成的直线上的条件是points[k].y-points[i].y)(points[j].x-points[i].x)==(points[j].y-points[i].y)(points[k].x-points[i].x)。算法总共是三层循环.
Time complexity: O(n^3)
Space complexity: O(1)
代码如下：

  public class Solution {
    public int maxPoints(Point[] points) {
        int result = 0, n = points.length;
        for (int i = 0; i < n; ++i) {
            int inSame = 1;
            for (int j = i + 1; j < n; ++j) {
                int newResult = 0;
                long a.x = points[i].x, a.y = points[i].y;
                long b.x = points[j].x, b.y = points[j].y;
                if (a.x == b.x && a.y == b.y) {
                    ++inSame;
                    continue;
                }for (int k = 0; k < n; ++k) {
                    int c.x = points[k].x, c.y = points[k].y;
                    if (a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - b.x*a.y - a.x * c.y == 0) {
                        ++newresultult;
                    }
                }
                result = Math.max(result, newResult);
            }
            result = Math.max(result, inSame);
        }
        return result;
    }
}

题解2：HashMap空间换时间
哈希表来记录斜率和共线点个数之间的映射，对每个点建立map，斜率是key。 计算斜率分数时，用gcd法。我们还需要顶一个变量duplicate来记录重合点的个数，与哈希表中数值相加，共线点个数总和。
Time complexity: O(n^2)
Space complexity: O(n)
代码如下：

  public class Solution{
        public int maxPoints(Point[] points) {
            if (points==null) return 0;
            if (points.length<=2) return points.length;
            int res=0;
            for (int i=0;i<points.length;i++){ 
                Map<String,Integer> map = new HashMap<>();
           //HashMap第一遍遍历所有点，第二遍还是遍历所有点，只要两个点不是同一个点，我们就求出这两两个点的斜率
             //key用来存斜率，value用来存当前斜率下点的个数
                int inSame=0;//定义两个变量用来表示两点重合的情况和在x轴上的情况
                int xAxis =0;
                 int l = points.length;
            for (int j = i + 1; j < l; j++) {
                int x = points[i].x - points[j].x;//分子
                int y = points[i].y - points[j].y;//分母
                if (x == 0 && y == 0) {
                    inSame++;
                    continue;
                }
                int gcd = helper(x, y);
                x /= gcd;
                y /= gcd;
                // 用string来存储斜率
                String slope = String.valueOf(x) + String.valueOf(y);
                int count = map.getOrDefault(slope, 0);
                count++;
                map.put(slope, count);
                xAxis = Math.max(xAxis, count);
            }
            res = Math.max(res, xAxis + inSame + 1);
        }
        return res;
    }
    public int helper(int x, int y) {//最大公约数函数，辗转相除法
        if (y == 0) return x;
        return helper(y, x % y);
    }
  }